package str;

public class Solution {

    /**
     * 541. 反转字符串 II
     * @param s
     * @param k
     * @return
     */
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        int n = arr.length;

        for (int i = 0; i < n; i += 2 * k) {
            int right = Math.min(i + k - 1, n - 1);
            reverse(arr, i, right);
        }

        return new String(arr);
    }

/*    private void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }*/

    /**
     * 151. 反转字符串中的单词
     *  1. 去除多余的空格 2.将这个字符串反转 3.每个单词分别反转
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        chars = removeExtraSpaces(chars);
        reverse(chars, 0, chars.length - 1);
        reverseEachWord(chars);
        return new String(chars);
    }

    public char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            if (chars[fast] != ' ') {
                // 如果不是第一个单词，需要在前面加一个空格
                if (slow != 0)
                    chars[slow++] = ' ';
                //拷贝整个单词
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow);
        return newChars;
    }

    public void reverse(char[] chars, int left, int right) {
        if (right >= chars.length) {
            return;
        }
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }

    public void reverseEachWord(char[] chars) {
        int start = 0;
        for (int end = 0; end <= chars.length; end++) {
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
}
